#pragma once

#include <cstdlib>
#include <cstdio>
#include <vector>

using namespace std;

class TreeNode
{
public:
	TreeNode(int val)
	{
		this->val = val;
		left = right = NULL;
	}
	TreeNode(int val, TreeNode* left, TreeNode* right)
	{
		this->val = val;
		this->left = left;
		this->right = right;
	}

	int val;
	TreeNode* left;
	TreeNode* right;
};

typedef vector<TreeNode*> NodePath;

TreeNode* CreateTree();

void PreOrderVisitTreeR(TreeNode* node);
void MidOrderVisitTreeR(TreeNode* node);
void PostOrderVisitTreeR(TreeNode* node);

void PreOrderVisitTree(TreeNode* node);
void MidOrderVisitTree(TreeNode* node);
void PostOrderVisitTree(TreeNode* node);

void LayerVisitTree(TreeNode* node);
void BreadthVisitTree(TreeNode* node);
void DepthVisitTreeR(TreeNode* node);
void DepthVisitTree(TreeNode* node);
void MaxMinDepth(TreeNode* node, int& max, int& min);

bool ValidateBST1(TreeNode* node, int preVal);
bool ValidateBST2(TreeNode* node, int min, int max);

bool FindNodePath(TreeNode* node, int target, NodePath& rPath);
TreeNode* LowestCommonAncestor1(TreeNode* node, int a, int b);
TreeNode* LowestCommonAncestor2(TreeNode* node, int a, int b);
TreeNode* LowestCommonAncestor3(TreeNode* node, int a, int b);